CS1.406 Advanced Algorithms (Spring 2023)

---

Announcements

• Teaching assistants: Amul Agarwal, Kunal Jain, Nithish Raja
• Schedule: Tuesday and Friday, 15:35 – 17:00
• Classroom: H103

Lectures

1. Introduction to Randomized algorithms, RandQS (Includes the list of tentative topics)

   • References: Chapter 1 of [1], Chapter 1 & Section 2.4 of [2]

2. Min-Cut, and Las Vegas & Monte carlo

   • References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].

3. Coupon collector’s problem, Markov Inequality, Chebyshev’s inequality

   • References: Section 3.6 of [1] and Chapter 3 of [2].

4. Minimum Spanning Trees, Boruvka’s algorithm

   • References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner

5. Karger-Klein-Tarjan Randomized Minimum Spanning Tree

   • References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner, Original paper of Karger-Klein-Tarjan.

6. Karger-Klein-Tarjan Randomized Minimum Spanning Tree (contd.)

   • References: Draft notes of Anupam Gupta (CMU), Survey by Jason Eisner, Original paper of Karger-Klein-Tarjan.

7. Introduction to Matroids

   • References: Extra material from Jeff Erickson’s book, NPTEL video of Prof. Shashank Mehta.

8. Matroids (contd.)

   • References: Extra material from Jeff Erickson’s book, NPTEL video of Prof. Shashank Mehta.

9. Introduction to Polynomial Identity Testing, Univariate Interpolation, Verifying Matrix Multiplication

   • References: Section 7.2 & 7.3 of [1], and Section 1.1 & 1.3 of [2].

10. DeMillo-Lipton-Schwartz–Zippel lemma, The isolation lemma and Mulmuley, Vazirani, and Vazirani algorithm for matching

    • References: Section 12.4 of [1], Section Moshkovitz’s alternate proof of DLSZ lemma, and Mulmuley-Vazirani-Vazirani ‘87

11. Concentration bounds

    • References: Chapter 4 of [2].

12. Chernoff bound, Error reduction, Set balancing

    • References: Chapter 4 of [2].

13. Randomized routing

    • References: Section 4.2 of [1], Section 4.5.1 of [2], Lovett’s course notes from UCSD, and J R Lee’s course notes from UWash.

14. Randomized routing (contd.), Maximum Satisfiability

    • References: Section 5.2 of [1], and Section 6.2.2 of [2].

15. MAXCUT, Derandomization with conditional probabilities

    • References: Section 6.2 and 6.3 of [2].

16. Introduction to Quantum Algorithms (guest lecture by Kannan Srinathan)

17. Shor’s integer factoring (guest lecture by Kannan Srinathan)

18. Approximate counting: DNFs

    • References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].

19. Random walks and Markov chains

    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

20. Markov Chains – 2SAT

    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

21. Markov Chains – 3SAT

    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

22. Goemans-Williamson algorithm for MAXCUT

    • References: Original paper of Goemans and Williamson.

References

1. R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
2. M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
3. N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.

Similar courses

1. Previous offering of the course - Spring 2022
2. See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).